1
Les bases de l'approximation par norme
MATH008Lesson 6
00:00
Imaginez que vous êtes un tailleur essayant d'ajuster une veste standard (l'espace des valeurs de $A$) à un client aux proportions uniques (le vecteur $b$). Quelle que soit la manière dont vous ajustez les manches ou la taille (les coefficients $x$), la veste ne sera jamais parfaitement ajustée. Vous cherchez le meilleur compromis — une approximation par norme qui minimise la tension ou le « résidu » à chaque couture.

Le cadre mathématique

L'objectif principal consiste à trouver un vecteur $x \in \mathbb{R}^n$ tel que la combinaison linéaire $Ax = x_1a_1 + \dots + x_na_n$ approche le mieux possible $b$. Cela est souvent appelé la régression de $b$ sur les variables explicatives (les colonnes de $A$).

Nous nous concentrons sur le vecteur résiduel $r = Ax - b$. En pratique, nous supposons un système surdéterminé où $m > n$. Pourquoi ? Parce que lorsque $m = n$ et que $A$ est inversible, le point optimal est simplement $A^{-1}b$, entraînant une erreur nulle — un cas trivial pour l'optimisation.

🎯 Principe fondamental
Le problème d'approximation par norme (6.1) est un problème convexe et est garantie d'être résoluble. Il existe toujours au moins une solution optimale $\hat{x}$ qui minimise la distance entre la cible et le sous-espace atteignable.

Variations canoniques

En fonction du type d'erreur que nous souhaitons pénaliser, nous choisissons différentes normes :

1. Moindres carrés ($\ell_2$)

La méthode la plus courante. Elle minimise la somme des carrés des résidus : $\|Ax - b\|_2^2$. Elle est sensible aux grandes anomalies, mais offre une solution analytique via les équations normales.

2. Chebyshev / Minimax ($\ell_\infty$)

Minimise le maximum absolu $\max_i |r_i|$. Cela est utilisé lorsque chaque mesure doit rester dans une tolérance stricte. Il peut être résolu via le programme linéaire suivant (PL) :

minimiser $t$
sous réserve que $-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$

3. Somme des résidus absolus ($\ell_1$)

Minimise $\sum |r_i|$. Cette approche est robuste aux anomalies, car elle ne met pas au carré les erreurs. Elle est également résoluble via un PL :

minimiser $\mathbf{1}^T t$
sous réserve que $-t \preceq Ax - b \preceq t$

Contexte d'estimation

Dans de nombreux domaines de l'ingénierie, nous supposons qu'un état réel $x$ est masqué par un bruit : $y = Ax + v$. Notre objectif est de trouver une estimation $\hat{x} = \text{argmin}_z \|Az - y\|$. En choisissant la norme, nous faisons implicitement une hypothèse sur la distribution statistique du bruit $v$.

\text{Minimiser } \|u - b\| \text{ sous réserve que } u \in \mathcal{A} \quad (\text{où } \mathcal{A} = \text{Image}(A))